package _77

import "sort"

/*
时间复杂度：O(N)
空间复杂度：O(N)

hash 先统计所有数字出现的次数，然后再遍历一次nums，判断当前元素v是否出现一次，且在hash中不存在v+1和v-1的key
*/

func findLonely(nums []int) []int {
	hash := make(map[int]int)
	for _, v := range nums {
		hash[v]++
	}
	ans := make([]int, 0)
	for _, v := range nums {
		if hash[v] == 1 && hash[v+1] == 0 && hash[v-1] == 0 {
			ans = append(ans, v)
		}
	}
	return ans
}

/*
时间复杂度：O(NlogN)
空间复杂度：O(logN)

排序+if
*/

func findLonely1(nums []int) []int {
	sort.Ints(nums)
	result := make([]int, 0)
	n := len(nums)
	if n == 1 {
		return []int{nums[0]}
	}
	for i, v := range nums {
		if (i == 0 && nums[i+1]-v > 1) || (i == n-1 && v-nums[i-1] > 1) ||
			(i > 0 && i < n && v-nums[i-1] > 1 && nums[i+1]-v > 1) {
			result = append(result, v)
		}
	}
	return result
}
